// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-27 11:33
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class NumSubmatrixSumTarget {
    /**
     * 元素和为目标值的子矩阵实现，朴素匹配方法
     */
    public int numSubmatrixSumTargetT(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        /*-----构造前缀和数组-----*/
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        /*-----子数组枚举-----*/
        //1 朴素枚举
        // i,j 为右下角 -> 通过p,q定位左上角
        int res = 0;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                for (int p = 1; p <= i; p++) {
//                    for (int q = 1; q <= j; q++) {
//                        if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == t) {
//                            res++;
//                        }
//                    }
//                }
//            }
//        }


        //2 优化枚举
        /*
            使用边标定子矩阵，同时使用isRight实现最大二分效益
            固定上下左三条边，移动右边形成大矩阵，左边的移动可以通过right-preRight的方式获取所有可能的子矩阵
         */
        // 2.1 优化枚举 ---最大hash效益
        boolean isRight = n < m;
        for (int top = 1; top <= (isRight ? n : m); top++) {
            for (int bot = top; bot <= (isRight ? n : m); bot++) {
                int right = 0;
                Map<Integer, Integer> map = new HashMap<>();
                for (int r = 1; r <= (isRight ? m : n); r++) {
                    right = isRight ? sum[bot][r] - sum[top - 1][r] : sum[r][bot] - sum[r][top - 1];
                    if (right == t) {
                        res++;
                    }
                    if (map.containsKey(right - t)) {
                        res += map.get(right - t);
                    }
                    map.put(right, map.getOrDefault(right, 0) + 1);
                }

            }
        }


//        for (int top = 1; top <= n; top++) {
//            for (int bot = top; bot <= n; bot++) {
//                /*
//                    Hash的作用是快速定位非固定左边的子矩阵
//                    key是preRight,value是sum
//                 */
//                int right = 0;
//                Map<Integer, Integer> map = new HashMap<>();
//                for (int r = 1; r <= m; r++) {
//                    right = sum[bot][r] - sum[top - 1][r];
//                    if (right == t) {
//                        res++;
//                    }
//                    if (map.containsKey(right - t)) {
//                        res += map.get(right - t);
//                    }
//                    map.put(right, map.getOrDefault(right, 0) + 1);
//                }
//            }
//        }
//        return res;
        return res;
    }


    /**
     * 空间优化实现
     */
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int m = mat.length, n = mat[0].length, res = 0;
        boolean isRight = n > m;
        /*-----枚举子矩阵-----*/
        for (int i = 1; i <= (isRight ? m : n); i++) {
            /*
                sum存储的是每一行或者每一列元素之和，通过a的叠加可以实现子矩阵之和的获取
             */
//            int[] sum = new int[(isRight ? m : n) + 1];
            int[] sum = isRight ? new int[n + 1] : new int[m + 1];
            Arrays.fill(sum, 0);
            for (int j = i; j <= (isRight ? m : n); j++) {
                Map<Integer, Integer> map = new HashMap<>();
                int a = 0;
                for (int r = 1; r <= (isRight ? n : m); r++) {
                    sum[r] += isRight ? mat[j - 1][r - 1] : mat[r - 1][j - 1];
                    a += sum[r];
                    if (a == t) {
                        res++;
                    }
                    if (map.containsKey(a - t)) {
                        res += map.get(a - t);
                    }
                    map.put(a, map.getOrDefault(a, 0) + 1);
                }
            }
        }
        return res;
    }


    @Test
    public void shout() {
        // int[][] mat = {{0, 1, 1, 1, 0, 1}, {0, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 1, 0, 1, 1, 0}, {1, 0, 0, 1, 0, 0}};
        int[][] mat = {{1, -1}, {-1, 1}};
        int t = 0;
        System.out.println(numSubmatrixSumTarget(mat, t));
    }
}
